package visualizer.client.algorithms.rbBst;

import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;
import visualizer.client.utils.VisualizerUtils;

/**
 * User: DDovzhenko
 * Date: 10.03.14
 * Time: 15:16
 */
public class RedBlackBSTUtils {
    public static final String RED = "red";
    public static final String BLACK = "grey";

    public static boolean isRed(BNode h) {
        return h != null && h.getInnerColor().equals("red");
    }

    public static void flipColors(BNode h) {
        // h must have opposite color of its two children
        if (! ((h != null) && (h.getLeftBNode() != null) && (h.getRightBNode() != null))) {
            return;
        }
        if (! ((!isRed(h) && isRed(h.getLeftBNode()) && isRed(h.getRightBNode()))
                || (isRed(h) && !isRed(h.getLeftBNode()) && !isRed(h.getRightBNode())))) {
            return;
        }
        h.setInnerColor(getOppositeColor(h));
        h.getLeftBNode().setInnerColor(getOppositeColor(h.getLeftBNode()));
        h.getRightBNode().setInnerColor(getOppositeColor(h.getRightBNode()));
    }

    private static String getOppositeColor(BNode h) {
        return isRed(h) ? BLACK : RED;
    }

    public static BNode rotateRight(BNode h) {
        if (h != null) {
            BNode x = h.getLeftBNode();
            h.setLeftBNode(x.getRightBNode());
            x.setRightBNode(h);
            x.setInnerColor(x.getRightBNode().getInnerColor());
            x.getRightBNode().setInnerColor(RED);
            return x;
        }
        return h;
    }

    public static BNode rotateLeft(BNode h) {
        if (h != null) {
            BNode x = h.getRightBNode();
            h.setRightBNode(x.getLeftBNode());
            x.setLeftBNode(h);
            x.setInnerColor(x.getLeftBNode().getInnerColor());
            x.getLeftBNode().setInnerColor(RED);
            return x;
        }
        return h;
    }


    public static BinaryTree copyRBTree(BinaryTree binaryTree) {
        binaryTree = binaryTree.copyTree(true);
        setDefaultOuterColorToTree(binaryTree.getRoot());
        return binaryTree;
    }

    private static void setDefaultOuterColorToTree(BNode node) {
        if (node == null) {
            return;
        }
        node.setOuterColor(VisualizerUtils.DEFAULT_OUTER_COLOR);
        setDefaultOuterColorToTree(node.getLeftBNode());
        setDefaultOuterColorToTree(node.getRightBNode());
    }

}
